package Review;

import javafx.scene.layout.Priority;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
class Student implements Comparable<Student>{
    public int age;
    public Student(int age) {
        this.age = age;
    }

    @Override
    public int compareTo(Student o) {
        return this.age - o.age;
    }
}
class IntCmp implements Comparator<Integer> {
    //此时底层的优先级队列就从一个小根堆变成了一个大根堆
    @Override
    public int compare(Integer o1, Integer o2) {
//        return o2 - o1;
        return o2.compareTo(o1);
    }
}
/*所有的集合类都是泛型的，所以需要传一个泛型参数*/
public class Text6 {
    //TopK问题
    /*由于整体建堆时间复杂度太高，此时1. 先将前k个元素建立成一个大根堆
    * 2. 然后用剩下的元素和堆顶元素进行比较，最后这个大根堆中所有的元素就是
    * 前k个最小的元素*/
    /*时间复杂度：O(N*logK) 建堆的时间复杂度：O(K),向上调整的时间复杂度：
    * O((N-K)*logK),由于K是很小的，所以忽略不计*/
    public static int[] smallestK2(int[] arr, int k) {
        //1.建立一个大根堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        //2.将数组中的前k个元素入堆
        for (int i = 0; i < arr.length; i++) {
            if (i < k) {
                //入堆
                maxHeap.offer(arr[i]);
            }else {
                int val = maxHeap.peek();
                if (val > arr[i]) {
                    maxHeap.poll();
                    maxHeap.offer(arr[i]);
                }
            }
        }
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = maxHeap.poll();
        }
        return tmp;
    }
    public static void main(String[] args) {
        int[] arr = {33,4,6,7,88,9};
        int[] tmp = smallestK2(arr,3);
        for (int i = 0; i < tmp.length; i++) {
            System.out.print(tmp[i] + " ");
        }
    }
    /*时间复杂度：O(N + O(K * logN)),建堆的时间复杂度是O(N)，弹出k个元素每次弹出
    * 都需要向上调整，时间复杂度：O(K * logN)*/
    public int[] smallestK(int[] arr, int k) {
        //1.建立一个小根堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        //2.取出数组中的每一个元素放到堆中
        for (int i = 0; i < arr.length; i++) {
            minHeap.offer(arr[i]);
        }
        int[] tmp = new int[k];
        //3.弹出k个元素放进数组中
        for (int i = 0; i < k; i++) {
            tmp[i] = minHeap.poll();
        }
        return tmp;
    }

    public static void main4(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(11);
        list.add(22);
        list.add(333);
        //此时可以传一个实现了Collection接口的类这样的参数，
        //PriorityQueue就自动把这个数组中的怨怒是拿出来，变成小根堆了
        PriorityQueue<Integer> queue = new PriorityQueue<>(list);

    }
    public static void main3(String[] args) {
        PriorityQueue<Student> queue = new PriorityQueue<>();
        queue.offer(new Student(10));
        queue.offer(new Student(5));
        System.out.println();
    }
    public static void main2(String[] args) {
        //堆（优先级队列） 标准库中的PriorityQueue底层是一个小堆
        //如果自己实现了比较器，传一个比较器的参数，此时就是变成了大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(new IntCmp());
        queue.offer(30);
        queue.offer(20);
        queue.offer(3);
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }
    public static void main1(String[] args) {
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        TextHeap textHeap = new TextHeap();
        textHeap.initElem(array);
        textHeap.createHeap();
        //textHeap.offer(80);
        System.out.println(textHeap.pop());
        System.out.println("aaaa");
    }
}
